\chapter{运行时空间组织}

    分配策略: 动态分配, 静态分配. 允许递归的语言不能使用静态分配, 如Pascal. 满足先申请后释放的用栈实现, 否则用堆实现.

    \section{Fortran语言的存储分配}

        \subsection{Fortran语言的特点}

            Fortran语言中, 过程不允许递归使用, 数组大小不会变化, 数据的性质完全确定.

            具有\textsf{可调数组}, 在运行时才确定数组的大小. 

            具有\textsf{公用区}, 具体来说有有名公用区和无名公用区, 这样可以从内存单元分配的层面上实现数据共享.

            具有\textsf{等价语句}, 实现了同一个程序段中的不同变量之间的存储空间等价, 可以采用并查集实现, 难点: 复杂变量, 方法是引入动态基准的坐标, 建立等价环.

        \subsection{分层分配策略}

            存在调用关系的模块在编译时可以利用DAG实现分层分配, 既节约了内存也不产生冲突. 执行时从底部向上分配, 不会同时执行时允许分配重复的内存.
            
            局部区中包含临时变量, 形式单元, 寄存器保护区和返回地址.

        \subsection{处理公共和等价语句}

            \subsubsection{公共和等价语句的逻辑结构}

                在符号表里设立公共元指示器栏CMP, 维护同一公共块中所有名字构成的\textbf{链}. 维护COMLIST表, 它保存了各个公共块对应的链的首尾元素以方便访问.

                等价语句采用环形的逻辑结构, 并且不同等价环有可能因为有相同的元素合并为一个. 如果涉及数组中的元素, 则需要引入\textsf{相对数}: $z=$ base $-j\times L$, 其中$L$是字数, 而
                \[j=(i_1-1)+(d_1\times i_2-1)+\cdots+d_i\times\cdots\times d_{n-1}\times(i_n-1)\]

            \subsubsection{讨论: 处理公共区中的等价元素}

                分配公用区遇到等价环中元素时, 直接将公共链中的当前地址分配给这个元素;

                分配非公用区遇到等价环中元素时, 将局部数据区的当前地址分配给这个元素所在等价环中相对值最小的等价元素, 并按照其余等价元素的相对地址将剩余等价元素分配完毕, 然后继续分配非公共区的下一个元素.

                分配时有上述区别是因为公共区分配条件更弱, 即其在公用区中的相对位置不会因为等价关系而改变.

            \subsubsection{先处理公共语句再处理等价语句}

                空间分配发生在所有公共和等价等说明性信息都被读入之后. 公共语句对空间分配的要求是``保持顺序'', 而等价语句的要求是``共享存储''. 先处理公共语句更为方便, 然后只要解决``冒头''即可.

    \section{动态分配: 简单栈式分配}

        使用简单栈式分配的前件: 没有分程序结构, 过程定义不允许嵌套, 允许递归调用, 允许局部可变数组(不允许全局可变数组). 用活动记录简单地构成一个栈.

        \subsection{活动记录}

            \textsf{活动记录}存储过程某次执行时的信息, 它满足一叉树的数据组织特征. 活动记录通常包括临时变量内情向量简单变量, 形参单元和个数, 返回地址, 各链链头, 形式单元以及局部数据区, 此外还有DISPLAY和全局DISPLAY. 多层调用的活动记录构成一个栈.

            活动记录中的老SP项(动态链)指向动态外层活动记录的SP, 作用是方便退出调用时清理活动记录栈. 返回地址项用于结束调用时的动态跳转. 全局DISPLAY, 返回地址和老SP合称\textsf{连接数据}.

        \subsection{动态分配中的非局部标识符调用}

            嵌套过程语言中, 过程可以引用其(静态)外层任意过程中的标识符, 通常实现的方法有\textsf{静态链}和\textsf{DISPLAY表}.

            \subsubsection{静态链}

                过程调用时引用非局部标识符是通过其定义时的\textbf{静态}结构实现的. 在活动记录中设置静态链指针, 它指向当前过程的直接外层的最新的一条活动记录的起始位置.

            \subsubsection{DISPLAY表}

                为了使得过程执行时知道所有(静态)外层过程的活动记录地址, 将他们构成DISPLAY表. DISPLAY表本质上是一个栈, 它可以包括在活动记录AR中. 

\vskip 2em
(完)
